1. Field
Various embodiments of the invention pertain to communication systems and more particularly, to a device and/or method for decoding data in digital communication systems.
2. Background
Communication systems use numerous techniques to increase the amount of information transferred while minimizing transmission errors. In these communication systems, the information is typically represented as a sequence of binary bits or blocks of bits called frames. The binary information is modulated to signal waveforms and transmitted over a communication channel. Communication channels tend to introduce noise and interference that corrupt the transmitted signal. At a receiver the received information may be corrupted and is an estimate of the transmitted binary information. The number of bit errors or frame errors depends on the amount of noise and interference in the communication channel.
To counter the effects of transmission channel corruption, error correction coding is often used in digital communication systems to protect the digital information from noise and interference and reduce the number of bit/frame errors. Channel coding is typically accomplished by selectively introducing redundant bits into the transmitted information stream. These additional bits allow detection and correction of bit errors in the received data stream thereby providing more reliable transmissions.
One type of error correction code, known as turbo code, has near-Shannon-limit error correcting performance. The basis of turbo coding is to introduce redundancy in the data to be transmitted through a channel. The redundant data helps to recover original data from the received data. A turbo code can achieve a transmission performance to within approximately 1 dB of the Shannon channel capacity.
A well-known axiom in communications theory is that a randomly chosen code of sufficiently large block length n is capable of approaching the Shannon channel capacity limit. However, the decoding of such a code increases with n up to a point where decoding becomes physically unrealizable.
One type of decoder for turbo codes is the Maximum A Posteriori (MAP) algorithm, also known as A Posteriori Probability (APP) algorithm. The MAP algorithm decodes a block by performing a forward recursion and then a reverse recursion of a binary trellis tree of the block to obtain a pair of state metrics for each state in the trellis. The forward recursion of the trellis tree decodes the block in the forward direction to obtain a first estimate (forward state metric) of the information sequence. The reverse recursion (also known as backward recursion) of the trellis tree decodes the block in the reverse direction to obtain a second estimate (reverse state metric) of the information sequence. In implementing conventional MAP algorithms, one problem is that storing the forward state metrics and reverse state metrics can take an extraordinary amount of memory even for a modest constraint length and code block length.
Another difficulty with conventional MAP algorithms is that the sequential processing (i.e., forward recursion and reverse recursion) may fail to satisfy a constraint on decoding time. Specifically, performing a forward recursion and then a reverse recursion of the binary trellis of a block may take a longer time than is permissible by rate sensitive applications. The decoding of a data block may take longer than expected by rate sensitive applications.